\documentclass[12pt,fleqn]{article}
\usepackage {psfig,epsfig} % para incluir figuras em PostScript
\usepackage{amsfonts,amsthm,amsopn,amssymb,latexsym}
\usepackage[brazil]{babel}
\usepackage[utf8]{inputenc}
\usepackage{graphicx}
\usepackage[T1]{fontenc}
\usepackage{geometry}
\usepackage[intlimits]{amsmath}
%alguns macros
\newcommand{\R}{\ensuremath{\mathbb{R}}}
\newcommand{\Rn}{{\ensuremath{\mathbb{R}}}^{n}}
\newcommand{\Rm}{{\ensuremath{\mathbb{R}}}^{m}}
\newcommand{\Rmn}{{\ensuremath{\mathbb{R}}}^{{m}\times{n}}}
\newcommand{\contcaption}[1]{\vspace*{-0.6\baselineskip}\begin{center}#1\end{center}\vspace*{-0.6\baselineskip}}
%=======================================================================
% Dimenses da pgina
\usepackage{a4}                       % tamanho da pgina
\setlength{\textwidth}{16.0cm}        % largura do texto
\setlength{\textheight}{9.0in}        % tamanho do texto (sem head, etc)
\renewcommand{\baselinestretch}{1.15} % espaamento entre linhas
\addtolength{\topmargin}{-1cm}        % espao entre o head e a margem
\setlength{\oddsidemargin}{-0.1cm}    % espao entre o texto e a margem
       
% Ser indulgente no preenchimento das linhas
\sloppy
 

\begin{document}

% Pginas iniciais
\include {capa}           % capa ilustrativa


\tableofcontents


% Numerao em romanos para pginas iniciais (sumrios, listas, etc)
%\pagenumbering {roman}
\pagestyle {plain}

\setcounter{page}{0} \pagenumbering{arabic}
  
\setlength{\parindent}{0in}  %espaco entre paragrafo e margem 
% Espaamento entre pargrafos
\parskip 5pt  

\newpage

%################################ SEÇÃO 1 ################################
\section{Introdução}

Computação natural baseia-se na natureza como fonte de inspiração para criação
de algoritmos e técnicas para solucionar problemas complexos. A utilização dos algoritmos inspirados na natureza (algoritmos
bio-inspirados) é motivada pelas características e comportamentos (e.g.
adaptação, auto-organização, \textit{feedback}, interação, entre outros) dos
sistemas biológicos \cite{LeandroNunes20071}. Nesse sentido, diversas técnicas têm sido
propostas baseadas nisso, a saber: algoritmos genéticos, redes neurais artificias, \textit{swarms
algorithms}, entre outras.

Atualmente, um dos conceitos que tem sido foco de estudo nessa área é o de
\textit{Swarm Intelligence}. \textit{Swarm Intelligence} tem com uma das
principais características a análise de comportamento de enxames
(\textit{swarm}) de diferentes colônias de ``insetos sociais'' (formigas, abelhas, vespas, cupins).
Nesses enxames, a partir das interações entre os indivíduos pode-se ampliar os
efeitos do comportamento individual, tendo assim, um comportamento coletivo.
Aspectos de autonomia, funcionamento distribuído e auto-organização podem
ser facilmente percebidos em enxame de insetos \cite{Webb}.

Na literatura, existem diversos algoritmos de \textit{swarms}, em especial,
pode-se destacar o  \textit{Particle Swarm Optimization} (PSO) e o \textit{Ant
Colony Optimization} (ACO). O primeiro refere-se a uma abordagem estocástica a
qual modela o comportamento social de animais, como um bando de pássaros, um
cardume de peixes, ou um enxame de abelhas que buscam um objetivo comum. O
segundo refere-se ao algoritmo de colônia de formigas inspirados no
comportamento de formigas e como elas interagem. A principal ideia é a interação indireta
entre as formigas com ausência de uma coordenação centralizada, por meio das
trilhas de feromônio deixadas, permitindo encontrar caminhos menores entre o ninho e a fonte de alimento.

No contexto deste trabalho, serão utilizados algoritmos de colônia de
formigas para solucionar problemas de otimização (problema do labirinto) e
aprendizado de máquina (agrupamento de dados). Os problemas tratados neste trabalho, de acordo com a especificação, seguem duas estratégias cada: uma refere-se a busca por alimentos, enquanto a
outra trata a questão do agrupamento de formigas mortas,
respectivamente.

\newpage
Nesse sentido, este trabalho apresenta uma metodologia e conceitos para
construção de soluções para tais problemas. Além disso, foi criado um
\textit{framework} baseado em colônia de formigas para ser instanciado e
aplicado em ambos os problemas (otimização e de aprendizado de máquina).

Este relatório está organizado da seguinte maneira: Na seção 2 é descrito
brevemente o arcabouço do algoritmo de colônia de formigas que serve de base
para implementação dos algoritmos para solução do problemas especificados para este trabalho. Na seção
3, alguns cenários de motivação biológica do algoritmo são apresentados. Na
seção 4 é tratado o problema do labirinto, caracterizado como um problema de
otimização. Na seção 5, toda a abordagem utilizada durante a modelagem e
experimentação do problema do agrupamento de dados é descrita. Por fim, são
dadas as conclusões sobre a experiência de implementação do trabalho prático 2.
\newpage

%################################ SEÇÃO 2 ################################
\section{Inspiração Biológica}

O algoritmo de colônia de formigas (ACO - \textit{Ant Colony Optimization}) é
baseado no comportamento real das formigas. As formigas a medida
que andam depositam uma substância chamada feromônio no caminho, formando uma trilha de feromônio,
e quando elas precisam escolher um caminho a seguir, escolhem, com maior probabilidade, o
caminho que possui a maior quantidade de feromônio. Dessa forma, pode-se
perceber que a comunicação entre as formigas é indireta e realizada por meio
do feromônio. O caminho ou trilha de feromônio é importante para uma formiga
achar o caminho de volta ao ninho ou para as outras formigas encontrarem a fonte de alimentos.

Por exemplo, para melhor compreensão, considere a Figura 1. Inicialmente, cada
formiga escolhe um caminho aleatoriamente. As formigas convergem para um dos
caminhos de acordo com a taxa de feromônio existente que as atrairá. Nesse caso,
as formigas que seguem o caminho mais curto vão depositar mais feromônio no
caminho. Dessa maneira, caminhos mais curtam terão a maior probabilidade de
concentrar feromônio. Vale salientar que o feromônio possui a característica de
evaporar, assim contribui também para o menor caminho ser escolhido. Para este
exemplo, como são caminhos de tamanhos diferentes as
formigas convergem para o camimho mais curto. Uma formiga percorre mais rápido 
o caminho curto, do que qualquer outra que percorre o caminho longo (considere
que as formigas andam com a mesma velocidade). Logo, será depositado mais
feromônio no caminho curto do que no longo, atraindo formigas para o caminho
curto.

\begin{figure}[!htb]
	\centering
		\includegraphics[scale=0.5]{images/classic_ant_example.pdf}
	\label{fig:pdsmodel}
	\caption{Exemplo do comportamento de formigas caminhando entre o ninho e a
	fonte de alimento.}
\end{figure}

Diante disso, pode-se perceber que as soluções não são representadas pelas
formigas, mas sim pelos caminhos percorridos por elas, de forma que uma formiga
constroe o caminho (solução candidata) incrementalmente, a medida que caminham
entre a fonte de alimento e o ninho. A quantidade de feromônio depositada é proporcional a qualidade da solução.
\newpage

Esse exemplo anterior é aplicável, tipicamente, em diversos problemas de
otimização como descoberta do caminho mínimo e roteamento \cite{Meisel}. A área de
aprendizagem de máquina também se inspira no comportamento de formigas para realizar agrupamento de
dados \cite{Vizine}. A Figura 2 ilustra o comportamento real de formigas para
agrupar corpos de formigas.

\begin{figure}[!htb]
	\centering
		\includegraphics[scale=0.5]{images/real_ant_clustering.pdf}
	\label{fig:pdsmodel}
	\caption{Formigas realizando a tarefa de agrupamento de corpos de
	 outras formigas.\cite{Webb}}
\end{figure}

Nesse caso, o comportamento real objetiva-se a agrupar corpos de formigas mortas
(criação de cemitérios) ou para separar lavas de acordo com o tamanho. Isso
serve de motivação para a área de aprendizagem de máquina para aplicar em
algoritmos de agrupamento de dados (\textit{data clustering}) \cite{Lumer}.

O problema do agrupamento consiste em separar um conjunto de dados em
grupos, com base em uma ou mais características desses dados. Essa
separabilidade é dada pela similaridade ou dissimilaridade dos dados, de forma que dados com
características similares formam grupos (\textit{clusters}). Essa relação de
similaridade é calculada por meio de uma função de distância existente entre os
dados inter e intra-cluster. Dessa forma, objetiva-se descobrir as regiões
densas e esparsas no um conjunto de dados, assim como caracterizá-lo.

Pela Figura 2, pode-se assumir que as formigas, inicialmente, estão dispostas de
forma aleatoriamente distribuída. Após algum tempo, os corpos começam a ser
empilhados, passando a formar grupos. Um comportamento análogo pode ser
realizado para agrupamento de dados, como será exposto no Problema 2 deste
trabalho.
\newpage

%################################ SEÇÃO 3 ################################
\section{Arcabouço do Algoritmo de Colônia de Formiga}

Para auxiliar o processo de implementação foi criado um arcabouço, chamado
XYZ, em linguagem C++ que consiste de uma composição de classes com
responsabilidades bem definidas (isto é, baixo acoplamento e alta coesão),
visando representar entidades (e.g., Formiga, Dado) e efetuar operações (e.g., agrupar, buscar por
menor caminho) requeridas pela abstração do algoritmo de colônia de formigas. Este arcabouço fornece recursos e
determina o fluxo de controle de execução do algoritmo de colônia de formigas.
Além disso, o arcabouço fornece a possibilidade de interface gráfica para
visualização de dados, para isso, foi adotada a biblioteca CImg\footnote{CImg
Library - http://cimg.sourceforge.net/}.

O projeto do \textit{framework} de colônia de formigas é baseado no
comportamento real de formigas para as duas abordagens comentadas na seção 2
(busca por alimento e agrupamento de formigas mortas). Por isso, o
\textit{framework} foi dividido em dois módulos, que compartilham algumas
funções. Um módulo é aplicável a classe de problemas de otimização
(abordagem de busca por alimento) e o outro módulo é direcionado à problemas de 
aprendizagem máquina (abordagem de agrupamento de formigas).


O \textit{framework} considera um algoritmo base para cada uma das abordagens,
como descrito nas subseções a seguir. A Figura 4 apresenta um diagrama de
classes resumido do \textit{framework}. Pode-se destacar duas classes bases, a
classe \textit{Ant} que trata especificamente problemas de otimização e a classe
\textit{AntClustering} que possui um relacionamento com a classe Ant e
direciona-se para problemas de agrupamento.

\subsection{Abordagem de Busca por Alimento}

A busca por alimento é baseada
no \textit{feedback} positivo do feromônio considerando um comportamento
coletivo, ou seja, a trilha de feromônio é determinante na definição de uma boa
solução para o problema. Outro característica importante nessa implementação é a
definição dos comportamentos da formiga, no caso, dependendo se a formiga está
procurando comida ou retornando ao ninho ela executa determinadas ações (e.g.,
liberar feromônio, verificar ferônomio na vizinhança).

Observando a classe Ant, podemos destacar as seguintes funções: 

\begin{itemize}
  \item \textit{SetBehavior(..):} Define o comportamento da formiga de acordo
  com o estado atual de busca por comida ou não;
  \item \textit{Walk(..):} As formigas caminham probabilistamente pela
  matriz/grafo de Pontos (instâncias da classe Point), dependendo do comportamento para dado
  instante.
  \item \textit{Roleta(..):} Chamada pela função \textit{Walk(..)} para
  determinar a probabilidade da direção da formiga, de acordo com o número de
  vizinhos possíveis para caminhar.
\end{itemize}

\begin{figure}[!htb]
	\centering
		\includegraphics[scale=0.5]{images/simulation_classic_example.pdf}
	\label{fig:pdsmodel}
	\caption{Execução do algoritmo de colônia de formigas aplicado ao
	\textit{framework}, seguindo o exemplo da Figura 1.}
\end{figure}

\clearpage




\subsection{Abordagem de Agrupar Formigas}

Na abordagem de agrupamento de dados baseada em algoritmo de colônia de
formigas temos duas classes bases no \textit{framework}: a classe Data que
representa os dados manipulados pelo algoritmo; e a classe AntClustering que
possui um relacionamento com a classe Ant e possui funções probabilísticas para
agrupar as instâncias da classe Data.

Basicamente, a utilização do \textit{framework} concentra-se na instanciação da
classe AntClustering, pois nela existem três funções bases que determinam o
processo de agrupamento. São elas:

\begin{itemize}
  \item \textit{Pick(..):} Função utilizada no processo de recolhimento de
  um dado do espaço de trabalho da formiga (mais detalhes na seção 5, por
  enquanto, considere o espaço de trabalho como uma matriz n x n dimensões).
  \item \textit{Drop(..):} Função responsável por determinar a probabilidade de
  uma formiga depositar um dado no espaço de trabalho;
  \item \textit{Walk(..):} Esta é uma variação da função \textit{Walk(..)} base.
  Ela é responsável por determinar a forma de como a formiga caminha no espaço
  de trabalho (em conjunto com a função \textit{go\_jumping\_data(..)}), de
  acordo com a densidade de dados na vizinhança. 
\end{itemize}

\begin{figure}[!htb]
	\centering
		\includegraphics[angle = 270, scale=0.6]{images/ModelClassesTP2.png}
	\label{fig:pdsmodel}
	\caption{Diagrama de Classes UML do Framework do Algoritmo de colônia de
	formigas.}
\end{figure}


%inicia uma nova pgina
\clearpage

%################################ SEÇÃO 4 ################################
\section{Problema 1: Labirinto}
\label{sec:tab}


\subsection{Descrição}

Como comentado na seção 1, algoritmos de colônia de formigas podem ser aplicados
para resolver problemas de otimização. Nesse sentido, para este trabalho prático, o problema de 
otimização a ser resolvido com o uso de algoritmo de colônia de
formigas é: encontrar o menor caminho válido possível entre a entrada e saída de
um labirinto.

O labirinto utilizado neste trabalho tem a seguinte representação:
\[
  m_{i,j} = 
   \begin{cases}
    0 & \text{se } m_{i,j} = corredor \\
    1 & \text{se } m_{i,j} = parede \\
   \end{cases}
\]

Uma matriz M com dimensões m x n, onde cada posição é definida como a função
acima. Dessa forma, para solucionar este problema, dados um ponto de partida
S$_{i,j}$ e um de chegada E$_{i,j}$ (com 0 < 1, k < m e 0 < j, l < n), encontrar
o menor caminho de S$_{i,j}$ a E$_{i,j}$. Então um caminho é válido se inicia em
S$_{i,j}$ e termina em E$_{i,j}$.  

A Figura 3 mostra como foi modelado a estrutura do labirinto para representar
parede e corredor. A Figura 5 (a) é a representação fornecida pela especificação
do trabalho. A Figura 5 (b) é a conversão da entrada original para uma
representação de 0s e 1s, como dito na equação acima. A Figura 5 (c) é a saída
do algoritmo após a definição do caminho. O caminho válido é denotado pelo
caminho formado pelo número 4, como mostra a Figura 5 (c). Na Figura 5 (d) temos
a representação gráfica fornecida pela instanciação do módulo
gráfico do \textit{framework}, a marcação de \textit{pixel} vermelha corresponde
ao ninho e a de verde corresponde à fonte de alimento. 


\begin{figure}[!htb]
	\centering
		\includegraphics[scale=0.5]{images/entrada_saida_lab.pdf}
	\label{fig:es_lab}
	\caption{Configurações de entrada e saída para o problema do labirinto.}
\end{figure}

\newpage 


\subsection{Modelagem}

Uma das tarefas mais importante na modelagem de um problema para ser solucionado
usando algoritmo de colônia de formigas é definir o processo de utilização do 
feromônio. Pelo que foi descrito anteriormente, partindo da posição inicial
S$_{i,j}$ dada, um caminho mínimo deve ser construído até o alvo. Para tanto,
as formigas irão visitar as posições livres do labirinto de acordo com a
quantidade de feromônio depositada.

As formigas inicialmente partem do ninho (posição inicial S) e aleatoriamente
caminham ao longo do labirinto. No momento que encontram a fonte de alimento
elas retornam ao ninho liberando o feromônio. Paralelamente, outras formigas
caminham no lab irinto selecionando a próxima posição de acordo com a quantidade
de feromônio observada.

A abordagem de busca por alimento do \textit{framework} foi aplicada
para este problema. O mapeamento do labirinto é feito por uma matriz de duas
dimensões, na qual as formigas caminham verificando se existe caminhos válidos
(não há paredes). Além disso, foi criada uma matriz auxiliar (chamada de
\textit{pherom\_map}) que armazena a quantidade de feromônio para cada posição
válida do labirinto. Então, a medida que as formigas caminham, elas verificam
nessa matriz a quantidade de feromônio. 

Na instanciação do \textit{framework}
foi considerado que a formiga possui três comportamento básicos (em C++, na
Figura 6), descritos a seguir:
\begin{itemize}
  \item Buscando alimento (\textit{searching\_food}): As formigas caminham
  probabilisticamente pelo labirinto considerando as posições válidas e a
  presença de feromônio;
  \item Retornando ao ninho (\textit{returning\_nest}): Para cada formiga é dada
  como parâmetro uma quantidade de energia para caminharem buscando comida. Caso
  a energia esgote (para cada passo uma quantidade de energia é gasta) e
  elas não tenham encontrado uma fonte de alimento, então essas formigas voltam
  para o ninho para iniciarem uma nova busca pela fonte de alimento ou na
  esperança de encontrar uma trilha de feromônio, dado que outras formigas podem
  ter encontrada alguma fonte de alimento;
  \item Carregando alimento (\textit{carring\_food}): Caso alguma formiga
  encontre uma fonte de alimento, ela retorna para o ninho carregando o alimento
  e liberando feromônio por um caminho válido.
\end{itemize}

\begin{figure}[!htb]
	\centering
		\includegraphics[scale=0.8]{images/ant_behaviors.pdf}
	\label{fig:es_lab}
	\caption{Estrutura que define os possíveis comportamentos de uma formiga.}
\end{figure}

A Figura 7 ilustra como esses comportamentos são representados em um labirinto.
Os \textit{pixels} vermelhos correspondem as formigas que buscam comida. Os
\textit{pixels} verdes correspondem as formigas estão carregando alimento e,
consequentemente, retornando para o ninho. Os \textit{pixels} amarelos
correspondem as formigas que estão retornando sem alimento para o ninho. Os
\textit{pixels} de cores cianos correspondem ao feromônio deixado pelas
formigas a medida que retornam para o ninho. A janela feromônio exibe as trilhas
de feromônio deixadas pelas formigas.

\begin{figure}[!htb]
	\centering
		\includegraphics[scale=0.6]{images/labirinto_comportamentos.pdf}
	\label{fig:es_lab}
	\caption{Instanciação dos comportamentos das formigas no \textit{framework}.}
\end{figure}


Esta implementação foi baseada na versão mais geral de ACO. Ela considera uma
função chamada \textit{desirability} que é utilizada para medir a qualidade de
uma componente para ser adicionada como uma solução candidata parcial. A função
\textit{desirability} é utilizada em conjunto com a quantidade de feromônio
associada a cada componente da solução candidata para compor a regra de
transição probabilística. Esta regra define que componente será inserido como
solução parcial e a probabilidade de escolher uma componente
\textit{i} é proporcional ao produto da \textit{desirability} pela quantidade de
feromônio.

Outra regra utilizada no ACO é a regra de atualização do feromônio, que
determina como atualizar a quantidade de feromônio relacionada com cada
componente. Considerando que o feromônio evapora, ele contribui para determinar
a qualidade da solução, visto que o caminho com maior quantidade de feromônio é
candidato a solução do problema.
                                                            
Usando essas regras citadas e considerando os comportamentos anteriormente
descritos, tem-se o seguinte algoritmo de colônia de formigas aplicado ao
problema do labirinto: Inicializa-se todas as formigas na posição de entrada do
labirinto com comportamento de busca por alimento; Em seguida, para as n
iterações faça: Cada formiga caminha segundo a regra de transição
proabilística; Quando uma formiga atinge uma fonte de alimento, avalia-se a
solução candidata, se uma melhor solução é encontrada, então atualiza a
melhor solução; Então, a formiga muda o comportamento para retornar ao ninho
liberando feromônio, se não encontrar uma fonte de alimento até que a energia
 acabe, então ela volta para o ninho sem liberar feromônio; 

\subsection{Experimentos}

Para a realização dos experimentos/testes foram adotados como base três
labirintos disponibilizados em conjunto com o documento de
especificação deste trabalho prático. No entanto, visando buscar uma maior validação da
implementação proposta, foram criados outros labirintos, apesar de não
discutidos nesta seção, eles estão no arquivo compactado e podem servir como
entrada para testes.

Os labirintos, como entrada, possuem uma estrutura semelhante ao da Figura 6
(a) e possuem dimensões grandes. Dada esta entrada, foi realizada uma
transformação para uma matriz binária Figura 6 (b), essa transformação foi necessária, pois
facilitou a representação do labirinto na forma gráfica da Figura 6 (d) quando
submetida ao \textit{framework}.

A Tabela 1 apresenta os parâmetros necessários para a execução do algoritmo de
colônia de formigas para o \textit{framework} proposto neste trabalho. Nas
colunas mais à esquerda temos os valores para cada labirinto para os quais
tivemos melhores resultados (Em termos de testes, aconselhamos executar o
labirinto M3, visto que este roda em poucos minutos, enquanto os outros
dois gastam mais tempo).

Alguns parâmetros são óbvios no algoritmo de colônia de formigas, já outros
parâmetros como as probabilidades 1 e 2 foram utilizadas para tornar o algoritmo
mais aleatório, por exemplo, uma formiga não caminha somente para a frente, ela
possui uma probabilidade de voltar a medida que caminha.
\begin{table}
\begin{center}
\begin{tabular}{|c|c|c|c|}
\hline
\hline
Parâmetros & M1 & M2 & M3\\
\hline
\hline
Arquivo executável & ./tp2\_p1 & ./tp2\_p1 & ./tp2\_p1\\
Nome do arquivo & M1.txt & M2.txt & M3.txt\\
Número de formigas & 500 & 600 & 300\\
Número de iterações & 500000 & 1000000 & 100000\\
Taxa de evaporação  & 0.0009 & 0.0003 & 0.002\\
Energia do feromônio da formiga  & 0.1 & 0.1 & 0.1\\
Energia da formiga & 150000 & 450000 & 30000\\
Tamanho da memória da formiga & 50 & 50 & 50\\
Parâmetro 1 da probabilidade & 100 & 100 & 100\\
Parâmetro 2 da probabilidade & 95 & 95 & 95\\
Tempo de atualização do display (ms) & 1 & 1 & 1\\
Valor de aumento do display (0 - não muda) & 1 & 1 & 1\\
\hline
\end{tabular}
\end{center}
\caption{Tabela de parâmetros para execução do algoritmo de formigas para o
problema do labirinto com as entradas M1, M2 e M3.}
\end{table}

Os resultados dos três labirintos de testes serão apresentados em ordem
crescente, de acordo com o número de passos válidos entre a entrada
(\textit{nest}) até a saída (\textit{food}). Dos três labirintos, nomeados
inicialmente de M1.txt, M2.txt e M3.txt, o M1 possue a menor distância entre a
entrada e a saída, para este foram contabilizados 271 \((\pm 0)\) passos. A
Figura 8 ilustra o trajeto identificado pelo algoritmo de colônia de
formigas para o labirinto 3 (M3.txt). 


\begin{figure}[!htb]
	\centering
	\label{maze3}
	\includegraphics[scale=0.7]{images/maze_3.png}
	\caption{Exemplo do comportamento das formigas caminhando entre o ninho e a
	fonte de alimento no labirinto 3.}
\end{figure}

A saída contabiliza o menor caminho válido e mostra o trajeto na interface
gráfica. Na janela Labirinto - ACO temos as formigas (pontos vermelhos) e o
feromônio (pontos cianos), já na janela Feromônio temos o nível de feromônio
(em tons de cinza) no trajeto identificado pelo algoritmo. Note que apenas um
caminho é definido, visto que não há caminhos alternativos no labirinto
fornecido.

Na sequência dos resultados em ordem de complexidade de busca pela saída, temos
o labirinto 1 (M1.txt). Para este labirinto, foram contabilizados um total de
942 \((\pm 0)\) passos para o menor caminho encontrado.

\begin{figure}[!htb]
	\centering
	\label{maze1}
	\includegraphics[scale=0.7]{images/maze_1.png}
	\caption{Caminho entre a saída e a entrada para o labirinto 1.}
\end{figure}

Observando a Figura 9, podemos perceber que inicialmente as
formigas exploram probabilisticamente os caminhos possíveis até alguma fonte de
alimento. As formigas descem pelo labirinto explorando os caminhos válidos e a
quando encontram a comida, voltam liberando feromônio. Como elas caminham
aleatoriamente podem encontrar trajeto que não levem até alguma fonte de
alimento, por isso, neste trabalho, foi considerado que as formigas possuem uma
quantidade de energia limitada e a medida que elas andam, decresce. Formigas
caminhando de volta para o ninho são mostradas como pontos amarelos
(comportamento \textit{returning\_nest}).

Ainda sobre a Figura 9, observando a janela de feromônio percebe-se que
existem vários caminhos, mas como esta quantidade de feromônio representa um
certo instante de execução do algoritmo, o melhor caminho tende a surgir ao passar do tempo, como já podemos identificar o trajeto
em tons de cinza, onde a maior intensidade de branco é o caminho encontrado e os
caminhos mais claros representa o feromônio evaporando.

Finalmente, o labirinto 2 possui o caminho mais extenso entre o ninho e a fonte
de alimento. O menor caminho válido identificado neste labirinto 2 possui 3033
\((\pm 0)\) passos.



\newpage
\newpage

%% ################################SEÇÃO 5################################
\section{Problema 2: Agrupamento de Dados}

\subsection{Descrição}

Como comentado na seção 1, algoritmos de colônia de formigas também podem ser
aplicados para resolver problemas de aprendizado de máquina. Nesse sentido,
para este trabalho prático, o problema de aprendizado de máquina a ser resolvido com o uso de
algoritmo colônia de formigas é: dado um conjunto de dados, agrupá-los em
subconjuntos que possuem características comuns.

Como descrito no documento de especificação do trabalho prático
2, cada instância dos dados é composta por um conjunto de características. Uma
instância pode ser representada vetorialmente, onde cada componente do vetor
\(\vec{v}\) refere-se a um atributo da instância e \(\vec{v}\) está no
espaço de atributos k-dimensional.

Como o objetivo deste trabalho é agrupar os dados de acordo com a similaridade,
métricas de similaridade como a distância euclidiana e similaridade de cosseno
foram adotadas. Para a primeira, quanto mais próximas estão as instâncias mais
similares elas são, enquanto a segunda considera que a medida que o ângulo entre
dois vetores (representam instâncias) é menor, então tem-se uma maior
similaridade entre essas instâncias.

\subsection{Modelagem}

Na etapa de modelagem do problema para resolução usando um algoritmo de colônia
de formigas foi aplicada uma transformação para mapear dados de um espaço
k-dimensional para um espaço bi-dimensional chamado de \textit{grid}, esse
espaço bi-dimensional corresponde as posições em qua os dados estão na colônia.
A colônia de formigas é modelada como um espaço bi-dimensional, chamado
\textit{workspace}, e nesse espaço de trabalho (\textit{workspace}) cada posição
contém somente um dado e/ou apenas uma formiga.

Diante disso, as formigas trabalham para organizar a colônia de forma que os
dados posicionados próximos no \textit{workspace} são dados similares no espaço
de atributos (k-dimensional). Esse mapeamento dos dados do espaço de atributos
para o espaço de trabalho é feito aleatoriamente, caso haja colisão um nova
alocação é realizada até que o dado seja posto em uma posição.

\begin{figure}[!htb]
	\centering
		\includegraphics[scale=0.6]{images/transform_feature_grid.pdf}
	\label{fig:es_lab}
	\caption{Função de mapeamento do espaço de atributos para a \textit{grid}.}
\end{figure}

A Figura 10 apresenta a função de mapeamento de atributos de um espaço
k-dimensional para a \textit{grid}. Ela recebe como parâmetros: a dimensão da
\textit{grid}, os dados e a quantidade de dados. A cada tentativa de alocação de
um dado verifica-se se a posição escolhida possue um dado, se sim repete o
processo de escolha, caso contrário, atribui o dado na posição livre. Na Figura
11, tem-se um exemplo de como dados podem ser dispostos no espaço de trabalho
de duas dimensões a partir do espaço de atributos de três dimensões, na
implementação atual esse mapeamento é feito de forma aleatória, como comentado
anteriormente.


\begin{figure}[!htb]
	\raggedright
		\includegraphics[scale=0.8]{images/espaco_vetorial.pdf}
	\label{fig:pdsmodel}
	\caption{Relação entre os dados do espaço de atributos e do espaço de trabalho 
	(Figura retirada do documento de especificação do trabalho).}
\end{figure}

Inicialmente, os dados são aleatoriamente distribuídos. Depois de algum tempo,
os dados começam a ser agrupados por similaridade. Para a realização desse
processo de agrupamento, duas probabilidades devem ser consideradas: a
probabilidade de uma formiga pegar um dado e a probabilidade de uma formiga
depositar um dado. Antes de entrarmos em detalhes sobre essas probabilidades, é
importante entender o conceito de similaridade média, que é dada pela seguinte
função:


\[
 f(x_i) = \left\{ 
  \begin{array}{l l}
    1/s^2 *

 \sum_{\substack{
   x_i \in Neigh 
  }}
 [1 - d(x_i, x_j)/\alpha]
 & \quad \text{se $f$ > 0}\\
    0 & \quad \text{caso contrário}\\
  \end{array} \right.
\]

A função \textit{f} calcula a densidade local de itens em torno de \(x_i\) e
\(f(x_i)\) é a medida de similaridade média de um item \(x_i\) com um outro
item \(x_j\) presente na vizinhança de \(x_i\). O parâmetro \(\alpha\) 
representa a escala de dissimilaridade e \(d(x_i, x_j)\) é a distância euclidiana entre duas
instância do espaço de atributos. Sabendo disso, pode-se obter as probabilidades
de uma formiga pegar ou soltar um dado, como segue: 

\begin{itemize}
  \item Os dados são recolhidos e depositados em uma nova posição com a
  probabilidade: \[p_p = (k_1/(k_1+f))^2,\] se \(k_1\) (uma constante) for muito
  menor que \textit{f}, então a probabilidade de pegar um dado em uma região com muitos
  dados é pequena;
  \item A probabilidade de uma formiga depositar um dado que ela está
  carregando é:  \(
 p_d = \left\{ 
  \begin{array}{l l}
    2*f(x_i) = 
 & \quad \text{se $f$ < \(k_2\) }\\
    0 & \quad \text{caso contrário}\\
  \end{array} \right.
\)\\
 onde \(k_2\) é um valor constante;
\end{itemize}

O algoritmo de colônia de formigas para agrupamento de dados inicia com a
disposição das formigas aleatoriamente no espaço de trabalho (os dados devem
ser atribuídos as posições da \textit{grid} como descrito anteriormente). Então,
cada formiga caminha pelas posições do espaço de trabalho que não possuem outras formigas e 
recolhem os dados de acordo com a probabilidade \(p_p\) e depositam os dados com
probabilidade de \(p_d\). 

\begin{figure}[!htb]
	\centering
		\includegraphics[scale=0.5]{images/result_teste400_6.png}
	\label{fig:es_lab}
	\caption{Conjunto de dados sintéticos A clusterizado com colônia de formigas.}
\end{figure}

Visando uma validação do framework, dois conjuntos de dados sintéticos (A
e B) foram produzidos, e então fizemos uma comparação com alguns métodos de
agrupamento de dados. Por exemplo, temos um conjunto de dados agrupado utilizando
o framework (Figura 12) e usando o K-means (Figura 13).

\begin{figure}[!htb]
	\centering
		\includegraphics[scale=0.7]{images/k_means_teste400.png}
	\label{fig:es_lab}
	\caption{Conjunto de dados sintéticos A clusterizado com k-means.}
\end{figure}


\clearpage

Na Figura 14 tem-se um processo de agrupamento de um conjunto de dados
sintéticos B que possue três classes. A saídas geradas pelo \textit{framework}
proposto neste trabalho mostra o comportamento das formigas durante a tarefa de agrupamento. Os
\textit{pixels} verdes representam a classe 1, os \textit{pixels} vermelhos
correspondem aos dados da classe 2 e os \textit{pixels} azuis
correspondem aos dados da classe 3. As formigas são representadas pelos
\textit{pixels} pretos e amarelos, sendo que os amarelos são formigas carregando
dado e os pretos são formigas procurando dado. Perceba, inicialmente, que os
dados são dispostos aleatoriamente e ao passar do tempo
pequenos grupos vão se formando, as iterações ocorrem até que existem a formação de grupos maiores que
definam as classes dos dados.

\begin{figure}[!htb]
	\centering
		\includegraphics[scale=0.7]{images/processo_cluster.pdf}
	\label{fig:es_lab}
	\caption{Processo de agrupamento utilizando o algoritmo de formigas
	para o conjunto de dados sintéticos B.}
\end{figure}

\subsection{Experimentos}

Para o processo de experimentação do algoritmo de colônia de formigas para
agrupamento de dados foram utilizados três coleções conhecidas da
literatura: Iris, Two-Moons, Wine. Cada coleção é composta por atributos,
separados por vírgulas, sendo o último a identificação do grupo (vale salientar que este atributo não foi
utilizado no cálculo das similaridades), como mostra a Figura 15.

\begin{figure}[!htb]
	\centering
		\includegraphics[scale=0.8]{images/cluster_description.pdf}
	\label{fig:es_lab}
	\caption{Formato de entrada dos \textit{datasets} de testes para o problema
	do agrupamento de dados.}
\end{figure}

Como esse processo de agrupamento está sujeito à variabilidades para cada
execução, a identificação dos agrupamentos foram replicadas, e para cada
replicação, foi feita uma análise, considerando a qualidade do agrupamento
segundo a métrica CVBeta.

\[
CV Beta = \frac{d_{intra\_cluster}}{d_{inter\_cluster}}
\]

A Tabela 2 apresenta os parâmetros necessários para a execução do algoritmo de
colônia de formigas para o \textit{framework} proposto neste trabalho. Nas
colunas mais à esquerda da tabela, temos os valores para cada cluster para os
quais tivemos melhores resultados (Em termos de testes, aconselhamos executar o
Iris, visto que este roda em poucos minutos, enquanto os outros
dois gastam mais tempo).

\begin{table}
\begin{center}
\begin{tabular}{|c|c|c|c|}
\hline
\hline
Parâmetros & Iris & Moon & Wine\\
\hline
\hline
Arquivo executável & ./tp2\_p2 & ./tp2\_p2 & ./tp2\_p2\\
\textit{Dataset File} & iris.csv & moon.csv & wine.dat\\
Tamanho da Grid/Workspace & 100 & 150 & 1000\\
Número de formigas & 10 & 20 & 20\\
Tamanho da vizinhança (5 x 5)  & 25 & 25 & 25\\
k1 da função pick  & 0.2 & 0.2 & 0.2\\
k2 da função drop & 0.2 & 0.2 & 0.2\\
alpha \(\alpha\) & 0.3 & 0.3 & 0.3\\
Tipo de Similaridade & 0 & 1 & 0\\
Tempo de atualização do display (ms) & 5 & 5 & 1\\ 
Valor de aumento do display(0 - não muda) & 5 & 3 & 1\\
\hline
\end{tabular}
\end{center}
\caption{Tabela de parâmetros para execução do algoritmo de formigas para o
problema de agrupamento de dados com as entradas Iris, Moon e Wine.}
\end{table}

Alguns parâmetros são óbvios no algoritmo de colônia de formigas, outros
parâmetros como as probabilidades 1 e 2 foram utilizadas para tornar o algoritmo
mais aleatório, por exemplo, estimar uma taxa de pick e drop, ela
possui uma probabilidade de ``pegar o dado'' ou depositá-lo a medida que
caminha no espaço de trabalho.

A Tabela 3 apresenta os valores de médias e desvios padrões para o
\textit{dataset} iris. Este \textit{dataset} possui três classes: Iris-setosa,
Iris-versicolor e Iris-virginica. A Figura 16 mostra a organização espacial do
\textit{dataset} no \textit{workspace}. Os pontos em amarelo são formigas
carregando dados, o cluster vermelho é a classe iris-setosa, os outros dois são
os clusters versicolor e virginica. Perceba uma separabilidade maior entre os
dados do setosa, em relação aos outros clusters. Os dados versicolor e virginica
possuem uma proximidade de similaridades, devido a isso podemos perceber a
interseção entre os grupos de dados. 

A distância inter-cluster pode ser maior ou menor, isso devido a aleatoriedade
com que as formigas agrupam os dados em uma região, dessa forma impacta diretamente no cálculo do CVBeta.
Então, se quanto menor o CVBeta melhor, visto que os dados de cluster diferentes
estão espacialmente distantes. Já se tivermos clusters próximos, então a
distância inter-cluster será baixa e consequentemente a CVBeta será alta. 

Dito isso, na Tabela 3 temos um CBeta pequeno para a iris, pois a setosa
contribui para uma maior distância inter-cluster. Isso fica mais evidente observando a
Tabela 4 e a Figura 17 referentes as informações de clusterização do conjunto de
dados moons.csv. O CVBeta é alto, pois temos uma distância inter-cluster
pequena, além do fato de não temos a formação de cluster separadamente adequada,
como mostra a Figura 17. Vale ressaltar que esses resultados sobre o moon.csv já
eram esperados devido ao conhecimento prévio sobre o comportamento dos dados
dess \textit{dataset}.


\begin{figure}[!htb]
	\centering
		\includegraphics[scale=0.8]{images/iris.png}
	\label{fig:es_lab}
	\caption{Clusters identificados pelo algoritmo de colônia de formigas e
	exibidos no \textit{workspace (framework)} para o dataset Iris.}
\end{figure}

\begin{table}
\begin{center}
\begin{tabular}{|c|c|c|c|c|c|c|}
\hline
\hline
 & setosa & versicolor & virginica & Intra-Cluster &
Inter-Cluster & CVBeta\\
\hline
\hline
 Média & 5,8568
 & 6,1764
 & 6,3064
 & 6,1302
 & 32,3480
 & 0,1911
 \\
Desvio Padrão & 0,5885
 & 0,3430
 & 0,4269
 & 0,1921
 & 3,4776
 & 0,0218
 \\

\hline
\end{tabular}
\end{center}
\caption{Tabela de valores para a média e desvio padrão para o \textit{dataset}
íris.}
\end{table}


\begin{figure}[!htb]
	\centering
		\includegraphics[scale=0.6]{images/moons.png}
	\label{fig:es_lab}
	\caption{Clusters identificados pelo algoritmo de colônia de formigas e
	exibidos no \textit{workspace (framework)} para o dataset Moons.}
\end{figure}

\begin{table}
\begin{center}
\begin{tabular}{|c|c|c|c|c|c|}
\hline
\hline
 & class-0 & class-1 & Intra-Cluster &
Inter-Cluster & CVBeta\\
\hline
\hline
 Média & 12,6832
 & 11,9799
 & 12,3323
 & 12,4639
 & 0,9894
 \\
Desvio Padrão & 0,5266
 & 0,3975
 & 0,3474
 & 0,3302 
 & 0,0049\\

\hline
\end{tabular}
\end{center}
\caption{Tabela de valores para a média e desvio padrão para o \textit{dataset}
Moons.}
\end{table}

%################################ SEÇÃO 6 ################################
\clearpage
\section{Conclusão} 

Algoritmos de colônia de formigas são usados para encontrar boas soluções para
problemas considerados difíceis. Tais problemas estão na maioria na classe de
problemas de otimização, onde os algoritmos existentes para solucioná-los
possuem complexidades de tempo exponencial. Neste trabalho foram considerados
dois problemas: um problema de otimização e um problema de aprendizado de
máquina. Por meio desses problemas, podemos observar as vantagens e desvantagens
dos ACOs. 

No problema 1, tratado neste trabalho prático 2, observou-se que o ACO é um
algoritmo mais adequado que o algoritmo genético (tratado no Trabalho Prático 1). Um ponto que
certamente torna ambos algoritmos complexos é a questão relativa ao ajuste de
parâmetros, de forma a termos uma melhor combinação.

Já com o problema de 2, relativo a área de aprendizagem de máquina, acreditamos
que a aplicação do algoritmo genético seja mais adequado que o algoritmo de
colônia de formigas. Os resultados obtidos pelo algoritmo genético se mostraram
mais interessante em termos de desempenho e acurácia.

Nesse sentido, objetiva-se realizar outros testes com diferentes tipos de
datasets, visando buscar o melhor ajuste para o algoritmo de clusterização e
aplicar o algoritmo de ACO à problema de roteamento, visando observar o
comportamento do algoritmo em cenários práticos com variáveis reais.


\clearpage
%Incluindo referncias bibliogrficas
\bibliographystyle{plain} %define o estilo         
\bibliography{bibliografia} %busca o arquivo



\end{document} %finaliza o documento